Space Text

The programmer take the spaces one by one and place them between words much like compositors of yore.

Computers now make desktop publishing possible. Publishing software allows users to display text in much the same way as it is displayed in books. This case study describes the development of a function that could be inserted into a word processing program to display text flush with the right and left margins.

Problem Statement

Write and test a function named SpaceText that will "space out" a line of text to a specified line length. (The function might be used by a word processing program to right-align lines of output.) SpaceText will have the following header:

def SpaceText(line, length, desiredLength, status):

The parameters for SpaceText are as follows:

• line is an array of characters, representing a line of text.
• length is the length of the line represented.
• desiredLength is the desired length of the line.
• status is a variable in which the result of the spacing-out process is recorded.

Assume that StringType has been defined in the program that will contain SpaceText as an array of at least desiredLength characters.

SpaceText should insert blanks evenly between words in the line, starting at the left, so that the line is exactly the desired length and there are no blanks at either end. SpaceText should also adjust length accordingly. A "word" is a sequence of non blank characters that either starts at the beginning of the line or is preceded by a blank, and either ends at the end of the line or is followed by a blank. Blank spaces already occurring between words should be preserved. It may be necessary to add one more blank between some pairs of words than between others.

SpaceText will not be able to insert blanks between words as specified under the following conditions:

• The line starts or ends with a blank.
• The length of the line is already longer than desired Length.
• The line contains no words.
• The line contains only one word.

In these cases, line and length should be left unchanged, and one of the following values should be returned in status:

• ENDBLANK, when the line starts or ends with a blank
• TOOLONG, when desiredLength is less than length
• EMPTYLINE, when length = 0
• ONEWORD, when only one word appears on the line

When none of these situations occurs, the value OK should be assigned to status. If more than one of the situations occur, any of the specified values should be assigned to status. Assume that the identifiers ENDBLANK,TOOLONG, EMPTYLINE, ONEWORD, and OK have been defined as values of type StatusType in the program that will contain SpaceText.

Suppose, for an example, that the desired line length is 10 characters.Some sample lines and the results SpaceText would return are given below. (The numbers indicate the length of the line.)

Other than using the types StringType and StatusType and the constants ENDBLANK, TOOLONG, EMPTYLINE, ONEWORD, and OK, SpaceText and the functions it calls should be independent of the remainder of the program.

Analysis

6.1 Show how SpaceText handles input with several blanks between words.

Analysis

6.2 According to the definition of "word," how many words appear in the line

That's no gentleman--that's my coauthor.

Analysis

6.3 When should SpaceText add a different number of blanks between some pairs of words than between others?

Analysis

6.4 Prove that the four exceptional situations described in the problem statement cover all the cases where it is not possible to insert blanks between words to fill the line to the desired length.

Analysis

6.5 Give examples of all situations in which more than one of the exceptional situations occur (examples of situations in which there are more than one possible value to return in status).

Analysis

6.6 Why is desiredLength a value parameter while the others are variable parameters?

Reflection

6.7 What are the advantages of making SpaceText independent of the rest of the program?

Application

6.8 Explain how SpaceText might be used in a word processor.

Testing

6.9 Does your text editor provide a way to fill lines so that they have a given length? If so, does it always fill from left to right? What does it do in the four exceptional situations? Experiment to find out.

Preparation

Solutions in this case study require understanding of loops, arrays, and data types (but not records).

Initial Approach

What is the problem asking for?

The problem statement says to write and test a function called SpaceText that inserts blanks between words in a line of text. This function is to be pretty much independent of the remainder of the program that contains it.

Stop & Predict

Will SpaceText contain any input statements? Why or why not?

What this means is that SpaceText will not have any side effects other than those specified that is, it will store a value in the status parameter and perhaps will change the values in the line and length parameters. It won't change or even use any global variables. It won't do any input or output,because that might interfere with whatever the calling program is doing. In particular, it won't read the values for the parameters; these are supplied by the calling program when SpaceText is called, and reading more values for the parameters would overwrite those they already contain!

How will SpaceText be tested?

For SpaceText to be tested, however, it clearly must be contained in a complete program. We will have to write it, as well as SpaceText itself. The test program is not part of the solution to the problem, but it is necessary to show that the function works correctly.

We've done the same kind of activity in earlier case studies. There, we applied the strategy of incremental development to test functions and functions a few at a time. This typically involved writing a driver program to read values, send them to the function, and then print out the result it returned. The difference is that we knew in earlier case studies what the remainder of the program looked like; here, we're not allowed to make any assumptions about the calling program.

Why would someone design a function without a program to accompany it?

This kind of programming happens often in team projects. Someone decides how to split up the solution to a problem; members of the team then design and develop pieces of the solution and put them all together afterward. If the pieces are sufficiently well specified, then the program should work perfectly.

A programmer may also wish to create a library of subprograms to use in future solutions. The contents of the library could be subprograms that perform common actions or computations.

Stop & Help

How could SpaceText be used in a program to align the left and right margins of text in paragraphs?

Why should the function be independent of the calling program?

In either situation, the advantages of designing the function to minimize its dependence on the calling program are clear. When programming in a team, one should make the tasks of the other team members as easy as possible. The more their code has to set up when calling a function, the more chances there are for errors. When preparing a function for a library, one should make it general, that is, usable in a variety of programs. The more dependent a subprogram is on the calling program, the less general it will be, and the fewer opportunities one will have to use it without modifying it.

It's good to make subprograms as independent of their caller as possible, even in code we write for ourselves, not intended for a library. Such modular code, able to be plugged into a program like an amplifier or tape deck module into a stereo system, will be useful in future programs. Moreover,it's more understandable; one can always look to the subprogram parameters to see what effect the subprogram has on the calling program, rather than having to look through the entire program listing for uses of global variables.

What will the program to test SpaceText do?

Back to the design of SpaceText. It won't be difficult to create a program to test SpaceText. In addition, if SpaceText needs incremental development, it would be nice to have a program for testing the increments already created. We can design test data for SpaceText using the black-box approach, without even knowing what the code is. Finally, inventing a test program will give us a sense of accomplishment about finishing part of the problem. Thus, we decide to start by designing a test program and test data.

The test program should read values for SpaceText's arguments, call SpaceText, then print the results as in earlier case studies. Including "input, process, output" in a loop will make it easier to test SpaceText on a variety of data.

Stop & Help

Describe the template needed to create an "input, process, output" loop.

The calling program needs to supply four things to SpaceText: a line, a length, a desired length, and a status variable. The line is just a character array; its contents and length can be read using the ReadLine function from the Is It Legal? programs. The desired length is an integer no greater than the maximum number of characters in the line; the ReadlnInteger function from Is It Legal? or a simpler function ReadDesired can be used to get this value. Here is the code:

while True:
ReadLine(line, length)
ReadDesired (desiredLength)
SpaceText(line, length, desiredLength, status)
print line, length, and status

How are the variable types defined?

All the variables must of course be declared. The problem statement says that line is of type StringType, an array of characters. For the purposes of testing, we can choose the size for the array. We code this as a Python constant, and declare the array as follows:

MAXSTRLEN = 30 # large enough for testing
line = "" # Array of characters

Similar declarations appeared in the programs for Roman Calculator Construction and Is It Legal?

The length and desiredLength variables will be declared as integers. But what about status? We aren't told much about it: only that it is of type StatusType, as are the constants ENDBLANK, TOOLONG, EMPTYLINE, ONEWORD,and OK. StatusType can be defined in several ways. Recall from The Calendar Shop and Is It Legal? that similar constants were defined as integers. We decide to do the same thing for the purposes of testing.

Stop & Consider

In what other ways can StatusType be defined?

(Note that SpaceText is not allowed to rely on StatusType being the same as integer. The problem statement says that ENDBLANK and so on may be used, but it doesn't say how, implying that we may make no assumptions about how they are defined.) The complete set of definitions and declarations is then

MAXSTRLEN = 30 # Large enough for testing
ENDBLANK = 1
TOOLONG = 2
EMPTYLINE = 3
ONEWORD = 4
OK = 5

StringType = ""
StatusType = 0

line = ""
length, desiredLength = 0
status = 0

How will the information be printed?

Our test program will print the line and its length after calling SpaceText. Printing the length is easy. Printing the line is an application of the "process every element of an array" template, where the "processing" is printing the element. We will be checking the output for correct spacing, so we should make this easier by including a line of column headings similar to those in the problem statement. Since the line and its length go together,we group these into a OutputLine function:

def OutputLine(line, length):
k = 0
print('123456789012345
678901234567890')
for k in range(0, length):
print(line[k], end='')
print("\n")
print('length = ' + str(length))
print("\n") # extra blank line for nice spacing

The value of status must also be printed. This is best done in its own function. We would like to see words in the output rather than numbers, so an if-else statement is appropriate:

if status == 'OK':
print('ok')
if status == 'ENDBLANK':
print('line ends with a blank')
if status == 'TOOLONG':
print('line is longer than desired')
if status == 'EMPTYLINE':
print('line is empty')
if status == 'ONEWORD':
print('line contains only one word')

After a stub for the SpaceText function is added, the test program is complete. It appears in the Python Code section.

Stop & Predict

What errors are likely to be detected during testing?

What data should be used to test the completed SpaceText function?

A complete specification includes a set of data. To complete the specification of the SpaceText function, we devise a set of test data, using the black-box approach. We repeat the approach used in earlier case studies of noticing numeric quantities associated with the problem. We choose data for which those quantities have their maximum legal values, their maximum legal values plus 1 and minus 1, their minimum legal values,and their minimum legal values plus and minus 1.

Stop & Predict

What numeric quantities are associated with this problem?

As in the Roman Calculator Construction program, we must be concerned with varying lengths of lines. Thus an empty line, a line of one character, and a line as long as possible are good test data choices. The number of blanks to add is another numeric quantity, so we make sure to test lines to which no blanks are to be added, lines where one blank is added, and lines to which the maximum number of blanks are added. The number of words leads us to include lines with no words, one word, and the maximum number of words.

Analysis

6.10 Design test data in each of the categories just mentioned, and indicate the results that SpaceText should produce for each set of input.

Reflection

6.11 Almost all the functions in the test program use line and length. It seems to be a waste of time to pass them as parameters to all the functions. What advantages are there to passing line and length as parameters?

Reflection

6.12 What subprograms would you put into your personal subprogram library? Why?

Modification

6.13 We can build some simple test cases into the test program and save ourselves the effort of always having to type them. Modify the test program so that, before it enters the "input, process, output" loop, it calls SpaceText on an empty line and on lines that begin and end with blanks.

Modification

6.14 The output produced by the test program makes it somewhat difficult to tell if the line being printed contains trailing blanks. Devise a better output format that would make this situation easier to see quickly, and modify the program to produce output in your revised format.

Alternative Designs for SpaceText

How is SpaceText designed?

With the test program as a secure base, we move on to the design of SpaceText. The problem statement says that "SpaceText should insert blanks evenly between words in the line, starting at the left, so that the line is exactly the desired length and there are no blanks at either end. SpaceText should also adjust length accordingly." We will need to figure out how many blanks to insert and how to insert them.

How many blanks need to be inserted?

It is easy to compute the number of blanks to insert by subtracting length from desiredLength. We will call this quantity numToInsert.

Stop & Predict

What values of numToInsert require special treatment?

If numToInsert is equal to 0, SpaceText should return line and length unchanged with status = OK. If numToInsert is less than 0, then the line is already longer than desired, so SpaceText should return line and length unchanged with status = TOOLONG.

As for doing the insertion of blanks, the problem statement suggests two possible decompositions. Both involve loops. One is to repeat some action once for each blank to insert:

for k in range(0, numToInsert):
...
...

The other decomposition is to repeat some action once for each word in line, or perhaps for each gap between words. In pseudocode:

for each gap in line, do the following:
insert the right number of blanks into the gap.

Which solution seems best?

The blank-by-blank approach sounds simpler, the gap-by-gap approach more efficient-since in general there will be fewer gaps than blanks to insert-and perhaps more elegant. We'll explore both approaches, the simpler one first.

Reflection

6.15 Which approach seems better to you, the blank-by-blank approach or the gap-by-gap approach? Why?

Reflection

6.16 What are probable advantages of working on the simpler solution first? What are possible?

Blank-by-Blank Approach

What action is to be repeated for each blank to be inserted?

The blank-by-blank approach, expressed in pseudocode, is as follows:

for k in range(0, numToInsert):
insert the kth blank in the correct place in line

The "correct place in the line" will be somewhere between words. The insertion operation will require a position in the line at which to insert the blank; thus the loop body will have to include code to find the insertion position.

How is the insertion position found?

One idea for refining the loop body is the following: at each iteration, the position of the next blank in line is found and the new blank inserted there. In pseudocode:

for k in range(0, numToInsert):
find the position of the next blank in line
insert the kth blank there

Stop & Predict

Will this work?

The problem statement requires that "blank spaces already occurring between words should be preserved" and that "SpaceText should insert blanks evenly between words." This solution inserts too many blanks into a gap that already contains more than one blank. Thus it's not enough merely to find the next blank in the line; the program must instead look for the nextgap as in the following pseudocode:

for k in range(0, numToInsert):
find the position of the next gap in line
insert the kth blank there

Stop & Help

Show how searching for the next blank andadding a blank there leads to incorrect results in the following line:

Hi. How are you? I'm fine. See you around.

Table 6.1 illustrates how insertion that cycles through the gaps in the line would work. It starts with a line of 17 characters and produces a line 27 characters long.

A variable is needed to keep track of the insertion position; we'll call it currentPosition. To cycle through the gaps, we need to find the position of a blank in the next gap; we'll call that gapPosition. Adding these refinements leads to the following pseudocode.

initialize currentPosition
for k in range(0, numToInsert):
gapPosition = the position of the next gap in line
insert the kth blank or gapPosition
currentPosition = gapPosition

One may notice a similarity between this loop and the loop in the week by week version of The Calendar Shop program:

startOfWeek = 1 - dayForFirst
for i in range(1, numberWeeks):
PrintWeek(StartOfWeek, numberDates)
StartOfWeek = startOfWeek + 7

Both loops involve a variable that's keeping track of a position. In the gap finding loop, it's a position in line; in the week-printing loop, it's a position (date) in the month. In each case, the loop begins with processing that involves the position. The last statement in the loop updates the position.

Since the position of the next gap in line is just a single integer and finding it requires no changes to any other variable, a function to return the position is appropriate. A descriptive name for this function is NextGapPosition.

Stop & Predict

How should current Position be initialized?

Stop & Predict

What should NextGapPosition return when the end of the line is reached?

NextGapPosition obviously needs line as a parameter. In addition, NextGapPosition needs to know where to start looking for the next gap; currentPosition is as good a place as any. Finally, it needs to know how long line is in order to know when to cycle back to the beginning. All of these can be value parameters, as is conventional with functions. Thus the header for NextGapPosition is

def NextGapPosition(line, length, currentPosition):

and the assignment statement

gapPosition = NextGapPosition(line, length, currentPosition)

can be used in the loop.

Stop & Predict

How is a gap detected?

What are the steps in NextGapPosition?

We now design NextGapPosition. One step in finding a gap is finding the position of a blank character. This is easy. It involves applying the "search an array" template introduced in Is It Legal? to line:

k = currentPosition
blankFound = false
while not blankFound:
if k > length:
action if k runs off the end of line
elif line[k] == BLANK:
blankFound = true
else:
k = k + 1

Should k reach the end of the line, it should start over at the beginning; the statement

k = 1

should replace the "action if k runs off the end of the line" above.

Finding a blank is not enough to detect a gap. A gap arises when a blank is preceded by a nonblank. Finding a nonblank-that is, skipping blanks-is done with the same template:

k = currentPosition
nonblankFound = false
while not nonblankFound:
if k > length:
k = 1
elif line[k] != BLANK:
nonblankFound = true
else:
k = k + 1

Stop & Predict

What will the preconditions of NextGapPosition be?

How is a blank preceded by a nonblank detected?

We must now put this code together. Careful design of NextGapPosition requires, as in earlier case studies, that we consider its preconditions and postconditions.

In general, when NextGapPosition is called, currentPosition will contain the location of the first blank in the previous gap. Thus, NextGapPosition should skip past any other blanks in that gap, skip all the nonblank characters following the last blank, and find the first blank in the next gap. It should work to add the blank-finding code to the end of the blank-skipping code and match up the variables they use. Here's the code:

k = currentPosition
nonblankFound = false
while not nonblankFound:
if k > length:
k = 1
elif line[k] != BLANK:
nonblankFound = true
else:
k = k + 1
blankFound = false
while not blankFound:
if k > length:
k = 1
elif line[k] == BLANK:
blankFound = true
else:
k = k + 1

At the end of the second loop, k should contain the position of the first blank in the next gap.

What conditions could cause problems?

With any loop, one should make sure it terminates. Suppose that line is all blank or contains no blanks. Either situation causes one of the two loops to continue infinitely. Thus NextGapPosition must not be called unless there are at least two words in line.

Stop & Predict

What will prevent SpaceText from calling NextGapPosition with only one word in the line?

We have assumed that line currentPosition is blank when NextGapPosition is called. We have not yet determined an initial value for currentPosition, however. What if line[currentPosition] is not blank when NextGapPosition is first called? This turns out not to cause a problem. The blank skipping loop exits right away, since there are no blanks to skip. Then the blank finding loop finds the position of the next blank.

We draw two conclusions. First, currentPosition may be initialized to 1 before the blank-insertion loop. This makes sense because we wish to find the first gap starting from the beginning of the line. Second, NextGapPosition returns the position of the first blank in a gap if it is called with currentPosition anywhere either in the word before the gap or in the gap that precedes that word, as shown in the diagram below.

Stop & Consider

Why not initialize currentPosition to 0?

How can the code be simplified?

The code just designed does more work than necessary. If there are at least two words in line when NextGapPosition is called, each loop will terminate in only one way when it finds a nonblank or a blank respectively. Thus the blankFound and nonblankFound variables can be eliminated. Furthermore, the declaration of currentPosition as a value parameter means that the function may change it without affecting its value in the calling program. The following code results.

def NextGapPosition(line, length, currentPosition):
while line[currentPosition] == BLANK:
currentPosition = currentPosition + 1
if currentPosition > length:
currentPosition = 1
while line[currentPosition] != BLANK:
currentPosition = currentPosition + 1
if currentPosition > length:
currentPosition = 1
NextGapPosition = currentPosition
return NextGapPosition

How is a blank inserted?

Inserting a blank is a three-step process similar to the process of compression that we used in replacing prefixes in Is It Legal? First, space for the blank needs to be created by moving all the characters after the insertion point over one space. Then the blank can be inserted in the space. Finally,the length of the line is updated. A descriptive name for this function is InsertOneBlank. An example, in which a blank is inserted into position 4, is illustrated as follows:

Shifting subsequent elements over one position:

Storing the blank:

Contents of line and length after insertion:

Stop & Predict

Characters after the insertion point can be shifted overfrom left to right or from right to left. Does it matter?

What are the parameters of InsertOneBlank?

InsertOneBlank has three parameters: line, length, and position. (We use position rather than gapPosition or currentPosition because this is a general insertion function that can be used in a variety of insertion applications.)Since line is expanded by the function, it must be a variable parameter; length must be updated to account for the newly added character, and so it must also be a variable parameter.

What is the pseudocode for InsertOneBlank?

InsertOneBlank involves another application of the "process every element of an array" template, where the "processing" is copying an element to the position immediately following it. As with compression in Is It Legal? the template is applied only to those elements at and following the insertion position. A careless programmer might fall into the trap of applying the template as follows:

for k in range(position,length):
line[k] = line[k-1]

Stop & Predict

What's wrong with this code?

This code has a serious flaw. The copying must proceed in the opposite order. Here's the code for the complete function.

def InsertOneBlank(line, length, position):
k = 0
for k in reversed(range(length, position)):
line[k] = line[k-1]
line[position] = BLANK
length = length + 1

Stop & Predict

This function still has a bug. Identify it.

What is the decomposition for the blank-by-blank solution?

The decomposition arrived at for the blank-by-blank solution is summarized in the outline below.

Insert blanks one blank at a time:
For each blank to insert, do the following:
Find the position of the next gap:
Find the next non blank on the line.
Find the next blank on the line, moving from the end
to the beginning if necessary.
Insert a blank there:
Move characters over to make room for it.
Store the blank.
Increase the line's length by 1.

What does SpaceText look like?

We now have all the pieces for the blank-by-blank version of SpaceText. It calls NextgapPosition and InsertOneBlank until all the blanks are inserted. We have not, however, yet dealt with the various exceptional cases mentioned in the problem statement: an empty line, a line that starts or ends with a blank, a line that's already longer than desired, or a line with only one word.

How are the exceptional cases handled?

The exceptional cases should be checked before NextGapPosition is called, since one of the preconditions to NextGapPosition is that line contains at least two words. The problem statement allows flexibility in the order in which the checks are made. Each exceptional case is handled by assigning the corresponding return value to sfofus. This leads to the following code:

if length == 0:
status = EMPTYLINE
elif (line[1] == BLANK) or (line[length] == BLANK): status = ENDBLANK
elif desiredLength < length:
status = TOOLONG
elif line contains no blanks:
status = ONEWORD
else:
space out the words using the blank-by-blank code

Stop & Help

Can the checks for the various exceptional cases be made in any order? Explain why or why not.

All we need is a boolean function that returns true if line contains a blank to complete this section. (We call it ContainsBlank.) The complete collection of subprograms is in the Python Code section.

Stop & Help

Write the boolean function

Stop & Consider

Why did we create a function Contains Blank rather than a function ContainsNoBlank?

How is the code tested?

Recall that we have already used the black-box approach to design a set of test data. It included the following categories of lines:

• an empty line
• a line containing one character
• a line containing MAXSTRLEN characters
• a line longer than desired
• a line exactly as long as desired
• a line where one blank is to be added
• a line where the maximum number of blanks is to be added
• a line with no words
• a line with one word
• a line with the maximum number of words
• a line that starts with a blank
• a line that ends with a blank
• a line that starts and ends with a blank

Now that the code is written, we can use the glass-box approach to augment the set of test lines. The loops in NextGapPosition suggest lines that contain words and gaps of one character, two characters, and the maximum number of characters. The cycling behavior should be exercised as well, so a line that requires a second pass of insertions should also be part of the test data.

Stop & Help

Devise a set of test lines for the code just designed, and test the code.

What bugs are encountered?

The coding and testing process reveals some bugs in this code. Blanks are inserted in incorrect places, even at the end of the line. SpaceText is too simple to contain that bug. InsertOneBlank seems to be inserting correctly, but in the wrong places. That narrows the bug to NextGapPosition, where we notice that the code says if currentPosition > MAXSTRLEN instead of if currentPosition > length.

Another flaw is that the last character of the line is not getting printed. We check OutputLine, but we had made sure it worked before. Apparently, the length OutputLine receives is incorrect. InsertOneBlank is the only routine that affects the length, so we check it to find (after some confusion) that the for loop is going from length downto position+1 rather than length+1 down to position+1.

Stop & Predict

What would be symptoms of off-by-one errors in NextGapPosition?

How can more evidence be found that a set of test lines is comprehensive?

The bugs we encountered and the large number of categories of test data we devised suggest that this function is highly susceptible to off-by-one errors. One technique for showing that a set of test data is likely to expose such an error is called mutation testing. It involves introducing common bugs into the program, then checking that at least one of the test lines causes the bug to be displayed. One might, for instance, remove a + 1 or replace it by a - 1 or a + 2. One might interchange the order of two statements, replace a > by < or >=, or vice-versa. Things we then should look for are errors in handling the ends of the line, of a word, or of a gap.

Stop & Help

Generate a set of "mutations" of the code just designed, and check that at least one of the test lines you've devised provides evidence of each mutation.

Application

6.17 Write the code for an insertion function that inserts a blank next to each blank in line rather than in each gap. (This was referred to in the commentary as the solution of a "careless programmer.")

Analysis

6.18 Give an example of a line with multiple blanks between words for which the careless programmer's approach works correctly.

Analysis

6.19 The stated precondition for NextGapPosition, that line contains at least two words, is stronger than necessary to avoid an infinite loop. What is the weakest possible requirement for line that ensures that NextGapPosition will return some value?

Analysis

6.20 Can either of the while statements in NextGapPosition be replaced by a repeat statement without adding an accompanying if statement? Why or why not?

Modification

6.21 Rewrite SpaceText to use only one position variable rather than two.

Reflection

6.22 Why is it best to make the two while loops in NextGapPosition as similar as possible?

Testing

6.23 What test lines will provide the best evidence that the NextGapPosition will find the first gap correctly? Briefly explain.

Debugging

6.24 What would happen if SpaceText did not test for the case of a line with initial blanks? How would such a line be treated?

Modification

6.25 The blank-finding loop in the first version of NextGapPosition used the double-negative expression not nonblankFound. Recode this loop so that it is easier to understand.

Gap-by-Gap Decomposition

What about adding blanks to each gap only once?

Rather than cycling, it must be possible to figure out how many blanks to add to each gap. The program would then go through the line only once,inserting the right number of blanks between each pair of words. This can be called the "gap-by-gap" solution. The example below illustrates this approach, again extending a line of length 17 to the desired length of 27.

The gap-by-gap decomposition will put the correct number of blanks in each gap rather than inserting a single blank in successive gaps until all the blanks are assigned.

To insert the right number of blanks we need to know how many gaps there are, find each gap, and insert the blanks. In pseudocode:

count the gaps in the line
for k in range(0, numberGaps) do the following:
find the kth gap
insert the correct number of blanks there

Finding the kth gap can probably be done as in the blank-by-blank solution. The hard parts seems to be to counting the gaps and figuring out how many blanks to insert in each gap.

Stop & Predict

What parts of the blank-by-blank decomposition can be recycled for the gap-by-gap decomposition?

How can the gaps be counted?

We devise a function for returning the number of gaps and call it GapCount. One idea for counting the gaps is to call NextGapPosition, counting gaps until the end of the line is reached.

Stop & Help

Why use a function for GapCount ?

Stop & Predict

Can NextGapPosition be used unchanged to count the gaps in the line? Explain why or why not.

This idea has several flaws, however. Repeated calls to NextGapPosition will return the positions of all the gaps, but NextGapPosition was designed to "wrap around" the line and return the first gap after returning the last gap. Furthermore, NextGapPosition isn't designed to work if there is only one word in line-but how do we know this before we count the gaps?

These problems can be solved by using a modified version of NextGapPosition. A better idea, however, is to return to the definition of gap on which NextGapPosition was based: a gap is signaled by a nonblank immediately preceding a blank. We can apply the "process every element of an array" template straightforwardly to scan line for occurrences of the non blank-blank pair:

def GapCount(line, length):
numGaps, k = 0
for k in range(0, length):
if (line[k] != BLANK) and (line[k+1] == BLANK):
numGaps = numGaps + 1
GapCount = numGaps
return GapCount

Stop & Help

What does GapCount return for a line containing no gaps? How about an empty line, a line for which length contains 0?

Stop & Help

What are the preconditions for GapCount?

What is the "correct number of blanks" to insert at each gap?

The next step is to figure out how many blanks to insert in each gap. Again, a table of values will help:

"Even distribution" of blanks into gaps suggests the use of the // function to get the number of blanks to add to each gap. The % function will give the number of remaining gaps, so we add these values to the table.

The table shows that the number of gaps with an extra blank is just the number of blanks % the number of gaps. This makes sense, since it's the remainder when an identical number of blanks have been added to each gap.

Stop & Help

Suppose (numToInsert // # gaps) + 1 blanks were inserted into each gap. How many gaps would have an extra blank?

How does blank insertion work?

Pseudocode for computing the number of blanks to insert according to the above discussion is the following:

for k in range 1, numGaps, do the following:
find the kth gap
insert(numToInsert // numGaps) blanks
if k <= numToInsert % numGaps then
insert one more blank

The blank insertion can be done with a loop around InsertOneBlank. Finding the kth gap involves maintaining a position variable as in the blank-by-blank version and finding the next gap each time through the loop.

What does the gap-by-gap version of SpaceText look like?

Putting these functions together and checking for special cases as in the blank-by-blank version yields the gap-by-gap version of SpaceText in the Python Code section.

Stop & Help

Devise cases and test the gap-by-gap version SpaceText. Use all the cases previously tested, plus additional test lines adjust described.

How is the code tested?

The glass-box approach suggests testing GapCount with a line that has a gap as early in the line as possible and as late in the line as possible. Test data previously devised are also suitable here. We also look for things that can go wrong. For instance, the code uses // and %, which do division and shouldn't divide by zero. We must make sure that division by zero never happens.

Stop & Help

How is the possibility of dividing by zero avoided?

Modification

6.26 Modify InsertOneBlank from the blank-by-blank solution to take an extra argument, the number of blanks to insert. Name the new function Insertblanks, and modify SpaceText to call it to insert blanks.

Modification

6.27 If the line is guaranteed to contain at least one gap, NextGapPosition can be used to count gaps as follows: it is called once to find the starting position of the first gap, then called repeatedly until it returns that starting position. Code a version of GapCount that uses this approach.

Debugging

6.28 Insert a bug into the gap-by-gap version of SpaceText, and get a fellow programmer to find the bug. Which bugs are hardest to find?

Analysis

6.29 The gap-by-gap version was alleged to be more efficient than the blank-by-blank version, since in general there will be fewer gaps than blanks to insert. Choose a number of test lines and count (or modify the function to count) the number of assignment statements that fill or copy array elements in each version of SpaceText. Does the gap-by-gap version do fewer assignments? Explain.

Improving the Program

What parts of SpaceText could be improved?

Both versions of SpaceText designed so far do a lot of shifting of characters, pushing characters one space to the right at each insertion. One may check this by analyzing the code by hand or by instrumenting it, that is, adding code that measures how many operations are executed by incrementing a variable each time a statement is executed. (Some Python environments allow these execution counts to be produced automatically.) All this shifting could take a lot of time, perhaps as many pushes per insertion as there are characters in line. A revision to the gap-by-gap version can eliminate this inefficiency.

What is an efficient way to insert the blanks?

Since insertions always happen from left to right in the gap-by-gap solution, once a gap is filled, that part of the line will remain unchanged. Thus, if SpaceText copies the contents of line into another array while it searches for gaps, it can add blanks to the new array instead of inserting them into line. No shifting is necessary with this approach. The diagrams below illustrate the two processes.

What are ways to code the more efficient algorithm?

One way to implement this algorithm would be to design a complex loop that copies as it searches for a gap. An approach that reuses more of the code already designed separates the process of finding the next gap from the process of copying. An outline for a revision using this approach is given below, with revisions in italics.

Insert blanks using a second array called newLine:
Count the gaps in line.
Determine how many blanks to insert.
Initialize newLine along with position variables for line and newLine.
For each gap, do the following:
Find the position of the next gap in line.
Copy characters into newLine from the old position
in line to the gap position in line.
Add the correct number of blanks to newLine.
Update the position variables for line and newLine.
Copy the last word from line to newLine.
Copy newLine back to line.

The code for finding the next gap can be used unchanged in this solution.

What code occurs more than once in this approach?

This approach requires a lot of copying from one array to another. This suggests that we design a general copying function that copies a given sequence of characters from one array to another. We'll call this function CopySequence.

Stop & Help

What will be the parameters of CopySequence?

How is CopySequence coded?

Two of CopySequence's parameters will be the source line (from which characters are copied) and the destination line (to which characters are copied). CopySequence will also need to know where in the source to start copying and where to finish, and where in the destination to start copying.The function heading for CopySequence follows; anticipating the usefulness of a copying function with any array, we give the parameters general rather than specific names.

def CopySequence(source, sourceStart,
sourceEnd, destination, destStart):

Stop & Help

Why is the starting position in the destination not the same as the starting position in the source?

To design CopySequence, we once again apply the template "process every element of an array." The relevant elements are those between positions sourceStart and sourceEnd; the "processing" done is copying the element into destination. One extra bit of work to do for each element copied is to increment the position in destination. Here's the code:

for k in range(sourceStart, sourceEnd+1):
destination[destStart] = source[k]
destStart = destStart + 1

We note that making destStart a variable parameter removes the need to update it in the SpaceText code. We do this, simultaneously renaming destStart to destPosition.

How are blanks added to the new line?

Blanks are always added to the end of newline in this approach. Thus we design a function AddBlanksToEnd, whose parameters will be the line, a position at which to add blanks, and the number of blanks to add. The position will be a variable parameter so that it will be updated when the function returns. Here's the code.

def AddBlanksToEnd(line, position, numBlanks):
k = 0
for k in range(0, numBlanks):
line[position] = BLANK
position = position + 1

Stop & Help

What are the preconditions and postconditions of AddBlanksToEnd?

How are calls to these functions connbined?

Putting it all together requires attention to the preconditions and post conditions of the various routines. Here's the code:

currentPosition = 1
newLinePosition = 1
numToInsert = desiredLength - length
numGaps = GapCount(line, length)
numPerGap = numToInsert // numGaps
numExtras = numToInsert % numGaps
for k in range(0, numGaps):
gapPosition = NextGapPosition(line, length, currentPosition)
CopySequence(line, currentPosition, gapPosition,
newLine, newLinePosition)
if k <= numExtras:
AddBlanksToEnd(newLine, newLinePosition, numPerGap+1)
else:
AddBlanksToEnd(newLine, newLinePosition, numPerGap)
currentPosition = gapPosition
CopySequence(line, currentPosition, length, newLine, newLinePosition)

The final program in the Python Code section contains the result. The test data devised for the earlier versions should suffice to test this one.

Debugging

6.30 Suppose an almost correct version of the program just designed prints the line exactly as entered, no matter how long. What simple thing was probably omitted?

Analysis

6.31 Choose a number of test lines and count (or modify the function to count) the number of assignment statements that fill or copy array elements in the revised version of SpaceText. Does the revised version do fewer assignments? Explain.

Modification

6.32 Modify the program just designed to use only one array (the argument to SpaceText), and to insert blanks into it from right to left rather than from left to right.

Application

6.33 Why might efficiency matter for this function?

Outline of Design and Development Questions

These questions summarize the main points of the commentary.

Initial Approach
What is the problem asking for?
How will SpaceText be tested?
Why would someone design a function without a program to accompany it?
Why should the function be independent of the calling program?
What will the program to test SpaceText do?
How are the variable types defined?
How will the information be printed?
What data should be used to test the completed SpaceText function?

Alternative Designs for SpaceText
How is SpaceText designed?
How many blanks need to be inserted?
Which solution seems best?

Blank-by-Blank Approach
What action is to be repeated for each blank to be inserted?
How is the insertion position found?
What parameters will NextGapPosition have?
What are the steps in NextGapPosition?
How is a blank preceded by a nonblank detected?
What conditions could cause problems?
How can the code be simplified?
How is a blank inserted?
What are the parameters of InsertOneBlank?
What is the pseudocode for InsertOneBlank?
What is the decomposition for the blank-by-blank solution?
What does SpaceText look like?
How are the exceptional cases handled?
How is the code tested?
What bugs are encountered?
How can more evidence be found that a set of test lines is comprehensive?

Gap-by-Gap Decomposition
What about adding blanks to each gap only once?
How can the gaps be counted?
What is the "correct number of blanks" to insert at each gap?
How does blank insertion work?
What does the gap-by-gap version of SpaceText look like?
How is the code tested?

Improving the program
What parts of SpaceText could be improved?
What is an efficient way to insert the blanks?
What are ways to code the more efficient algorithm?
What code occurs more than once in this approach?
How is CopySequence coded?
How are blanks added to the new line?
How are calls to these functions combined?

Programmers' Summary

This case study considers the problem of adding blanks between words in a line of text to fill it out to a specified length. Three solutions are described. One is organized around a blank-by-blank loop that adds a single blank at a time to successive gaps between words. The second is organized around a loop that makes one pass through the line, inserting the correct number of blanks into each gap. Finally, a version of the gap-by-gap solution is considered in which a copy of the line was used to avoid the inefficiency of in-place insertion of blanks.

The problem statement specifies that a function called SpaceText be designed and developed. The program in which the function will be included is unspecified. This requirement is nothing new; functions have been tested in isolation in every case study so far.

Apart from using predefined types for strings and status values and predefined constants for status values, the function is also required to be independent of the calling program. This is a new requirement, illustrating new dimensions of the Recycling and Divide and Conquer principles

The goal of the problem is not to build an entire structure, but to build a component, a building block that can be used in a variety of programs. The more modular-independent of its surroundings-such a component is,the easier it is to use, both in a personal library of code for templates, and for team members working on a large program.

The problem statement introduces the use of a status variable, a more flexible and general way to gather and report on exceptional conditions that arise during processing. In our test program, we implement the status variable as an integer. Each status message is associated with a value for the integer. To ease implementation, following the Literacy principle, we give each condition a name such as ARRAYTOOLONG.

The line of text is represented in an array. Arrays in earlier case studies were used in relatively static ways. For example, the only dynamic change to an array in Roman Calculator Construction was to substitute single Roman digits for prefix pairs. Here, the whole point is to add new elements to the array. The use of box diagrams as in Is It Legal?, with arrows to show the direction of copying, provides a good alternative representation of the process (applying the Multiple Representations principle).

One array template is recycled directly: "search a one-dimensional array." Another, "process every element of an array," is specialized to (a) copy an array segment, (b) process elements while accumulating or updating a separate piece of information, and (c) shift elements of an array to make room for an insertion. These template specializations seem likely to occur in future applications.

The blank-by-blank approach illustrates how templates can be recycled to achieve a relatively short and uncomplicated program. This preliminary solution is used as a basis for a more efficient solution. Sometimes a quest for efficiency leads to code that's more complicated than necessary. However, when we add the auxiliary line array, we reject the complicated decomposition of copying while searching for a gap in favor of one that splits the searching and copying operations and therefore applies templates in a more straight forward way.

Analysis is important in the design. The two loops in NextGapPosition that skip blanks and search for the next blank are coordinated by matching the postcondition of one with the precondition of the other. The conditions under which these loops would fail to terminate determine the precondition of NextGapPosition and therefore dictate the order of exceptional-case testing in the main SpaceText routine. Analysis also reveals that the blank-by-blank program does a lot of character shifting. (This analysis may be done by hand, by instrumenting the code with variables that count how many times certain sections are executed, or by taking advantage of features of the programming environment that provide counts of the number of times each statement in a program is executed.) The gap-by-gap design, in combination with the use of an auxiliary array, eliminates the need for shifting, at the cost of having to recopy the expanded line back into the original array.

Integer arithmetic with // and % shows up yet again, this time to compute how many blanks should be inserted in each gap.

The test program for SpaceText is designed before the function (partly as a confidence builder). It includes output that makes clear the column positions within the line, to make it easier to notice errors. Much of the test data are designed beforehand as well, using the black-box approach to complete the problem specification. As in previous case studies, we notice numeric quantities associated with the problem and choose test data that bring these quantities to their extreme values. Because there are a lot of quantities, the function is somewhat difficult to test.

One suggested way of providing more confidence in the test data is mutation testing, in which bugs are intentionally introduced into the function to make sure that they are exposed during testing. (We do this after fixing a couple of unintentionally introduced bugs.) There is ample opportunity to associate bugs-typically off-by-one errors-with their symptoms, as suggested in the Fingerprint principle.

Making Sense of Space Text

Modification

6.34 Instead of characterizing a gap as a nonblank followed by a blank, one may instead consider a gap to arise from a blank followed by a nonblank. Rewrite each version of SpaceText to base the location of a gap on this new definition.

Analysis

6.35 What happens in each version of SpaceText if the check for a line ending with a blank is omitted?

Modification

6.36 Modify each version of SpaceText to take an extra boolean parameter that specifies whether the insertion of blanks should proceed left to right or right to left, and to insert blanks appropriately. In which version of SpaceText is this modification made most easily?

Modification

6.37 Modify each version of SpaceText to use a data structure consisting of two arrays, one containing the words in the line, the other containing the number of blanks that follow each word in the line. The new SpaceByGaps will change the number of blanks after each word so that the total line length is as desired. An illustration of the new data structure appears on the next page.

Hi. How are you? I'm fine. See you around.

Testing

6.38 To test and debug the modification described in question 6.37, you will need to change the ReadLine and OutputLine functions as well as the functions that insert blanks. Suppose you were going to change and test one routine at a time, in order to be as sure as possible that bugs in one routine don't affect the behavior of another. In what order should you make the changes to ReadLine, OutputLine,and the insertion routines, and how would you test them?

Modification

6.39 In modern typesetting systems, characters have different widths.The letter "w," for instance, is wider than the letter "i." The width of each character is expressed in number of pixels (picture elements);"w" might be 11 pixels wide and "i" only 3. Suppose we have defined an array charTable (standing for "charactertable") of the following type and included a routine ReadCharToble that fills each element of the array with the width in pixels of each character. Now we wish to use the table of widths to fill a line so that its width in pixels is a particular length. Modify each version of SpaceText to do this. Assume that a blank is one pixel wide.

Analysis

6.40 Once the modification of question 6.39 has been made, how do the relative efficiencies of the blank-by-blank version and the gap-by-gap version compare?

Reflection

6.41 Which of the three versions is easiest for you to understand? Which contains code that will be easiest for you to reuse? Which do you prefer? Explain.

Linking to Previous Case Studies

Modification

6.42 Modify the subprograms in Is It Legal? to return a status value rather than a boolean value. If there is an error in the argument, the status value should indicate what's wrong.

Modification

6.43 Modify the week-by-week version of The Calendar Shop to implement a three-step process: fill an array with the values 1,2, ..., up to the number of days in the month being printed; insert zeroes at the start of the array to represent the blank spaces at the beginning of the month; print the array, seven values to a line, substituting blanks for zeroes.

Test Program

# Test Program
# Insert blanks between words in the line as described in the problem statement.

def SpaceText(line, length, desiredLength, status):
status = OK
return status

# Print the line so that its length can easily be determined.

def OutputLine(line, length):
k = 0
print('1234567890
1234567890
1234567890')
for k in range(0, length):
print(line[k], end='')
print("\n")
print('length = ' + str(length))
print("\n") # extra blank line for nice spacing

def WritelnStatus(status):
if status == OK:
print('ok')
if status == ENDBLANK:
print('line ends with a blank')
if status == TOOLONG:
print('line is longer than desired')
if status == EMPTYLINE:
print('line is empty')
if status == ONEWORD:
print('line contains only one word')

# main program

MAXSTRLEN = 30
ENDBLANK = 1
TOOLONG = 2
EMPTYLINE = 3
ONEWORD = 4
OK = 5
BLANK = ' '
StringType = ""
StatusType = 0
line = ""
length = 0
desiredLength = 0
status = 0
while True:
length = 0
# Read a line, discarding characters that don't fit in a string.
line = input()
length = len(line)
# Read the desired length.
print('How long do you want the line to be? ')
desiredLength = int(input())
status = SpaceText(line, length, desiredLength, status)
WritelnStatus(status)
OutputLine(line, length)

Blank-by-Blank Solution

# Blank-by-Blank Solution

"""Return the position of the next gap (space between words) in line, starting the search at position currentPosition. If searching reaches the end of the line, restart it at the beginning of the line. Precondition: line must contain at least one blank."""

def NextGapPosition(line, length, currentPosition):
while line[currentPosition] == BLANK:
currentPosition = currentPosition + 1
if currentPosition >= length:
currentPosition = 0
while line[currentPosition] != BLANK:
currentPosition = currentPosition + 1
if currentPosition >= length:
currentPosition = 0
NextGapPosition = currentPosition
return NextGapPosition, currentPosition

# Insert a single blank into line at the given position.
# The line length increases by one.

def InsertOneBlank(line, length, position):
k = 0
line1 = list(line)
line1.insert(position, BLANK)
line = ''.join(line1)
length = length + 1
return line, length

def ContainsBlank(line, length):
k = 0
ContainsBlank = False
for k in range(0,length):
if line[k] == BLANK:
ContainsBlank = True
return ContainsBlank

# Insert blanks between words in the line as described in the problem statement.

def SpaceText(line, length, desiredLength, status):
numToInsert = 0
currentPosition = 0
gapPosition = 0
k = 0
if length == 0:
status = EMPTYLINE
elif (line[0] == BLANK) or (line[length-1] == BLANK):
status = ENDBLANK
elif desiredLength < length:
status = TOOLONG
elif not ContainsBlank(line, length):
status = ONEWORD
else:
numToInsert = desiredLength - length

currentPosition = 1
for k in range(0, numToInsert):
gapPosition, currentPosition = NextGapPosition(line, length, currentPosition)
line, length = InsertOneBlank(line, length, gapPosition)
currentPosition = gapPosition
status = OK
return status,line,length

def OutputLine(line, length):
k = 0
print('1234567890
1234567890
1234567890')
for k in range(0, length):
print(line[k], end='')
print("\n")
print('length = ' + str(length))
print("\n") # extra blank line for nice spacing

def WritelnStatus(status):
if status == OK:
print('ok')
if status == ENDBLANK:
print('line ends with a blank')
if status == TOOLONG:
print('line is longer than desired')
if status == EMPTYLINE:
print('line is empty')
if status == ONEWORD:
print('line contains only one word')

# main program

MAXSTRLEN = 30
ENDBLANK = 1
TOOLONG = 2
EMPTYLINE = 3
ONEWORD = 4
OK = 5
BLANK = ' '
StringType = ""
StatusType = 0
line = ""
length = 0
desiredLength = 0
status = 0
while True:
length = 0
# Read a line, discarding characters that don't fit in a string.
print("Enter a Line")
line = input()
length = len(line)
# Read the desired length.
print('How long do you want the line to be? ')
desiredLength = int(input())
status,line,length = SpaceText(line, length, desiredLength, status)
WritelnStatus(status)
OutputLine(line, length)

Gap by Gap Solution

This code uses some of the functions from the blank-by-blank solution.

def NextGapPosition(line, length, currentPosition):
while line[currentPosition] == BLANK:
currentPosition = currentPosition + 1
if currentPosition >= length:
currentPosition = 0
while line[currentPosition] != BLANK:
currentPosition = currentPosition + 1
if currentPosition >= length:
currentPosition = 0
NextGapPosition = currentPosition
return NextGapPosition, currentPosition

# Insert a single blank into line at the given position.
# The line length increases by one.

def InsertOneBlank(line, length, position):
k = 0
line1 = list(line)
line1.insert(position, BLANK)
line = ''.join(line1)
length = length + 1
return line, length

def ContainsBlank(line, length):
k = 0
ContainsBlank = False
for k in range(0,length):
if line[k] == BLANK:
ContainsBlank = True
return ContainsBlank

def GapCount(line, length):
numGaps = 0
k = 0
for k in range(0, length-1):
if (line[k] != BLANK) and (line[k+1] == BLANK):
numGaps = numGaps + 1
GapCount = numGaps
return GapCount

# Insert blanks between words in the line as described in the problem statement.

def SpaceText(line, length, desiredLength, status):
numToInsert = 0
currentPosition = 0
gapPosition = 0
numGaps = 0
k = 0
j = 0
if length == 0:
status = EMPTYLINE
elif (line[0] == BLANK) or (line[length-1] == BLANK):
status = ENDBLANK
elif desiredLength < length:
status = TOOLONG
elif not ContainsBlank(line, length):
status = ONEWORD
else:
numToInsert = desiredLength - length
currentPosition = 0
numGaps = GapCount(line, length)
for k in range(0, numGaps):
currentPosition = NextGapPosition(
line, length, currentPosition)
for j in range(0, numToInsert // numGaps):
line, length = InsertOneBlank(line, length, currentPosition)
if k < numToInsert % numGaps:
line, length = InsertOneBlank(line, length, currentPosition)
status = OK;
return status,line,length

def OutputLine(line, length):
k = 0
print('1234567890
1234567890
1234567890')
for k in range(0, length):
print(line[k], end='')
print("\n")
print('length = ' + str(length))
print("\n") # extra blank line for nice spacing

def WritelnStatus(status):
if status == OK:
print('ok')
if status == ENDBLANK:
print('line ends with a blank')
if status == TOOLONG:
print('line is longer than desired')
if status == EMPTYLINE:
print('line is empty')
if status == ONEWORD:
print('line contains only one word')

# main program

MAXSTRLEN = 30
ENDBLANK = 1
TOOLONG = 2
EMPTYLINE = 3
ONEWORD = 4
OK = 5
BLANK = ' '
StringType = ""
StatusType = 0
line = ""
length = 0
desiredLength = 0
status = 0
while True:
length = 0
# Read a line, discarding characters that don't fit in a string.
print("Enter a Line")
line = input()
length = len(line)
# Read the desired length.
print('How long do you want the line to be? ')
desiredLength = int(input())
status,line,length = SpaceText(line, length, desiredLength, status)
WritelnStatus(status)
OutputLine(line, length)

Revised Gap-by-Gap Solution

# Revised Gap-by-Gap Solution
"""Copy characters from positions sourceStart through sourceEnd of source to destination starting at position destPosition. Update destPosition to be one past the position in destination of the last character copied."""

def CopySequence(source, sourceStart, sourceEnd, destination, destPosition):
k = 0
destination = list(destination)
for k in range(sourceStart, sourceEnd+1):
destination.insert (destPosition, source[k])
destPosition = destPosition + 1
destination = ''.join(destination)
def AddBlanksToEnd(line, position, numBlanks):
k = 0
line = list(line)
for k in range(1, numBlanks):
line.insert(position, BLANK)
position = position + 1

# Insert blanks between words in the line as described in the problem statement.

def SpaceText(line, length, desiredLength, status):
numToInsert = 0
currentPosition = 0
newLinePosition = 0
newLine = ""
gapPosition = 0
numGaps = 0
k = 0
numPerGap = 0
numExtras = 0
if length == 0:
status = EMPTYLINE
elif (line[1] == BLANK) or (line[length] == BLANK):
status = ENDBLANK
elif desiredLength < length:
status = TOOLONG
elif not ContainsBlank(line, length):
status = ONEWORD
else:
currentPosition = 1
newLinePosition = 1
numToInsert = desiredLength - length
numGaps = GapCount(line, length)
numPerGap = numToInsert // numGaps
numExtras = numToInsert % numGapsv
for k in range(1, numGaps):
gapPosition = NextGapPosition(line, length, currentPosition)
CopySequence(line, currentPosition, gapPosition, newLine, newLinePosition)
if k <= numExtras:
AddBlanksToEnd (newLine, newLinePosition
, numPerGap + 1)
else:
AddBlanksToEnd (newLine, newLinePosition, numPerGap)
currentPosition = gapPosition + 1;
CopySequence(line, currentPosition,
length, newLine, newLinePosition)
line = newLine
length = desiredLength
status = OK